#ifndef INTERVIEWONE_H
#define INTERVIEWONE_H
#include <iostream>
#include "../../algorithms/datastruct/BinaryTree.h"
using namespace CLRS;
class InterviewOne
{
public:
	static void Convert2DoubleLinkedSeq(TreeNode<int,int>* node,
								   TreeNode<int,int>*& head,
								   TreeNode<int,int>*& tail)
	{
		head = tail = NULL;
		if (node == NULL)
		{
			return;
		}
		TreeNode<int,int>* tempHead,*tempTail;

		if (node->leftNode != NULL)
		{
			Convert2DoubleLinkedSeq(node->leftNode,tempHead,tempTail);
			head = tempHead;
			tempTail->rightNode = node;
			node->leftNode = tempTail;
		}
		if (node->rightNode != NULL)
		{
			Convert2DoubleLinkedSeq(node->rightNode,tempHead,tempTail);
			tail = tempTail;
			tempHead->leftNode = node;
			node->rightNode = tempHead;
		}
		if (head == NULL)
		{
			head = node;
		}
		if (tail == NULL)
		{
			tail = node;
		}
	}
	static void Run()
	{
		BinaryTree<int,int> tree;
		int arr[] = {10,6,14,4,8,12,16};
		for (int i = 0;i<sizeof(arr) / sizeof(int);i++)
		{
			tree.Insert(new TreeNode<int,int>(arr[i]));
		}

		//
		TreeNode<int,int> *head,*tail;
		Convert2DoubleLinkedSeq(tree.GetRoot(),head,tail);
		PrintOut(head);
	}
	static void PrintOut(TreeNode<int,int>* node)
	{
		while (node!=NULL)
		{
			std::cout << node->key << endl;
			node = node->rightNode;
		}
	}
};
#endif